package com.example.javamaday.leetcode.sort;

public class LcSort0912_04 {

    public static void main(String[] args) {

    }


    // 快速排序
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort(int[] nums, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int i = partition(nums, lo, hi); // 切分数组，并返回切分的index
        sort(nums, lo, i - 1);  // 按照上述规则，继续排序左半部分
        sort(nums, i + 1, hi);   // 按照上述规则，继续排序右半部分
    }

    private int partition(int nums[], int lo, int hi) {
        // 将数组切分为 a[lo...i-1], a[i], a[i+1...hi]
        int i = lo;
        int j = hi + 1;
        while (true) {
            // 从左往右找第一个数比基准值num[lo]大的索引
            while (nums[++i] < nums[lo]) {
                if (i == hi) {
                    break;
                }
            }
            // 从右往左找第一个数比基准值num[lo]小的索引
            while (nums[--j] > nums[lo]) {
                if (j == lo) {
                    break;
                }
            }
            // i 和 j 碰撞时，退出循环
            if (i >= j) {
                break;
            }
            exchage(nums, i,j);
        }
        // 此时i和j肯定碰撞了，这里传i或者j都行
        exchage(nums, lo, j);
        return j;
    }

    private void exchage(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}
